package org.dromara.business.sensitive;

import java.util.*;

public class ACAutomaton {
    private final ACNode root = new ACNode();

    public void build(List<String> keywords) {
        for (String word : keywords) {
            ACNode node = root;
            for (char c : word.toCharArray()) {
                node = node.children.computeIfAbsent(c, k -> new ACNode(k));
            }
            node.isWord = true;
            node.word = word;
        }

        Queue<ACNode> queue = new LinkedList<>();
        for (ACNode child : root.children.values()) {
            child.fail = root;
            queue.offer(child);
        }

        while (!queue.isEmpty()) {
            ACNode current = queue.poll();
            for (Map.Entry<Character, ACNode> entry : current.children.entrySet()) {
                char ch = entry.getKey();
                ACNode child = entry.getValue();

                ACNode fail = current.fail;
                while (fail != null && !fail.children.containsKey(ch)) {
                    fail = fail.fail;
                }

                child.fail = (fail != null) ? fail.children.get(ch) : root;
                queue.offer(child);
            }
        }
    }

    public List<SensitiveWord> match(String text) {
        List<SensitiveWord> result = new ArrayList<>();
        ACNode node = root;

        for (int i = 0; i < text.length(); i++) {
            char c = text.charAt(i);

            while (node != root && !node.children.containsKey(c)) {
                node = node.fail;
            }

            node = node.children.getOrDefault(c, root);

            for (ACNode temp = node; temp != root; temp = temp.fail) {
                if (temp.isWord) {
                    int start = i - temp.word.length() + 1;
                    result.add(new SensitiveWord(temp.word, start, i));
                }
            }
        }

        return result;
    }

    public String replace(String text, char mask) {
        List<SensitiveWord> hits = match(text);
        if (hits.isEmpty()) return text;

        // 合并重叠命中区间
        List<int[]> ranges = mergeRanges(hits);
        char[] chars = text.toCharArray();

        for (int[] range : ranges) {
            for (int i = range[0]; i <= range[1]; i++) {
                chars[i] = mask;
            }
        }
        return new String(chars);
    }

    // 合并区间
    private List<int[]> mergeRanges(List<SensitiveWord> hits) {
        List<int[]> merged = new ArrayList<>();
        hits.sort(Comparator.comparingInt(SensitiveWord::getStart));

        int start = -1, end = -1;
        for (SensitiveWord word : hits) {
            if (start == -1) {
                start = word.getStart();
                end = word.getEnd();
                continue;
            }

            if (word.getStart() > end) {
                merged.add(new int[]{start, end});
                start = word.getStart();
                end = word.getEnd();
            } else {
                end = Math.max(end, word.getEnd());
            }
        }
        if (start != -1) {
            merged.add(new int[]{start, end});
        }
        return merged;
    }
}
